package Chapter2;

public class CirDoubleList<T> {
    public DoubleNode<T> head;

    public CirDoubleList() {
        this.head = new DoubleNode<T>();
        this.head.prev = this.head;
        this.head.next = this.head;
    }

    public CirDoubleList(T[] values) {
        this();
        DoubleNode<T> rear = this.head;
        for (int i = 0; i < values.length; i++) {
            rear.next = new DoubleNode<T>(values[i], rear, this.head);
            rear = rear.next;
        }
        this.head.prev = rear;
    }

    public CirDoubleList(CirDoubleList<T> list) {
        this();
        this.copy(list);
    }

    public void copy(CirDoubleList<T> list) {
        this.clear();
        DoubleNode<T> rear = this.head;
        for (DoubleNode<T> p = list.head.next; p != list.head; p = p.next) {
            rear.next = new DoubleNode<T>(p.data, rear, this.head);
            rear = rear.next;
        }
        this.head.prev = rear;
    }

    public T get(int i) {
        DoubleNode<T> p = this.head.next;
        for (int j = 0; p != null && j < i; j++)
            p = p.next;
        return (i >= 0 && p != null) ? p.data : null;
    }

    public void set(int i, T x) {
        if (x == null)
            throw new NullPointerException("x=null");
        DoubleNode<T> p = this.head.next;
        for (int j = 0; p != null && j < i; j++)
            p = p.next;
        if (i >= 0 && p != null)
            p.data = x;
        else throw new IndexOutOfBoundsException(i + "");
    }

    public int size() {
        int i = 0;
        for (DoubleNode<T> p = this.head.next; p != this.head; p = p.next)
            i++;
        return i;
    }

    public String toString() {
        String str = this.getClass().getName() + "(";
        for (DoubleNode<T> p = this.head.next; p != this.head; p = p.next)
            str += p.data.toString() + ((p.next != this.head) ? "," : "");
        return str + ")";
    }

    public String toPreviousString() {
        String str = this.getClass().getName() + "(";
        for (DoubleNode<T> p = this.head.prev; p != this.head; p = p.prev)
            str += p.data.toString() + ((p.prev != this.head) ? "," : "");
        return str + ")";
    }

    public void print() {
        System.out.println("(");
        for (DoubleNode<T> p = this.head.next; p != this.head; p = p.next) {
            System.out.println(p.data.toString());
            if (p.next != this.head)
                System.out.println(",");
        }
        System.out.println("),(");
        for (DoubleNode<T> p = this.head.prev; p != this.head; p = p.prev) {
            System.out.println(p.data.toString());
            if (p.prev != this.head)
                System.out.println(",");
        }
        System.out.println(")");
    }

    public T remove1(int i) {
        DoubleNode<T> p = this.head.next;
        for (int j = 0; p != this.head && j < i; j++)
            p = p.next;
        if (p != head && i >= 0) {
            p.prev.next = p.next;
            p.next.prev = p.prev;
            return p.data;
        }
        return null;
    }

    public void clear() {
        this.head.next = this.head;
        this.head.prev = this.head;
    }

    public boolean isEmpty() {
        return this.head.next == this.head;
    }

    public DoubleNode<T> insert(int i, T x) {
        if (x == null)
            return null;
        DoubleNode<T> front = this.head;
        for (int j = 0; front.next != this.head && j < i; j++)
            front = front.next;
        DoubleNode<T> q = new DoubleNode<T>(x, front, front.next);
        front.next.prev = q;
        front.next = q;
        return q;
    }

    public DoubleNode<T> insert(T x) {
        if (x == null)
            return null;
        DoubleNode<T> q = new DoubleNode<T>(x, head.prev, head);
        head.prev.next = q;
        head.prev = q;
        return q;
    }

    public DoubleNode<T> search(T key) {
        for (DoubleNode<T> p = this.head.next; p != this.head; p = p.next) {
            if (key.equals(p.data))
                return p;
        }
        return null;
    }

    public T remove2(T key) {
        DoubleNode<T> find = search(key);
        if (find != null) {
            find.prev.next = find.next;
            find.next.prev = find.prev;
            return find.data;
        }
        return null;
    }

    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!(obj instanceof CirDoubleList<?>))
            return false;
        DoubleNode<T> p = this.head.next;
        CirDoubleList<T> list = (CirDoubleList<T>) obj;
        DoubleNode<T> q = list.head.next;
        while (p != this.head && q != list.head && q.data.equals(q.data)) {
            p = p.next;
            q = q.next;
        }
        return p == this.head && q == list.head;
    }

    public void addAll(CirDoubleList<T> list) {
        DoubleNode<T> rear = this.head.prev;
        rear.next = list.head.next;
        list.head.next.prev = rear;
        rear = list.head.prev;
        rear.next = this.head;
        this.head.prev = rear;
        list.head.prev = list.head;
        list.head.next = list.head;
    }

    public T removeLast() {
        DoubleNode<T> p = this.head.prev;
        if (p != head) {
            p.prev.next = this.head;
            this.head.prev = p.prev;
            return p.data;
        }
        return null;
    }

    public boolean contains(T key) {
        return this.search(key) != null;
    }

    public void concat(CirDoubleList<T> list) {
        CirDoubleList<T> list1 = new CirDoubleList<T>(list);
        addAll(list1);
    }

    public CirDoubleList<T> union(CirDoubleList<T> list) {
        CirDoubleList<T> this1 = new CirDoubleList<T>(this);
        CirDoubleList<T> list1 = new CirDoubleList<T>(list);
        DoubleNode<T> rear = this1.head.prev;
        rear.next = list1.head.next;
        list1.head.next.prev = rear;
        rear = list1.head.prev;
        rear.next = this1.head;
        this1.head.prev = rear;
        list1.head.prev = list1.head;
        list1.head.next = list1.head;
        return this1;
    }
}
